This invention relates to the selection of channels in wireless communications networks, and in particular for ad hoc communications networks. An important factor in deploying any radio network as the avoidance of co-channel interference between transmitters operating at the same frequency. Conventionally, network architectures are planned in advance, and the necessary infrastructure is then deployed according to that plan. However, this approach may be impractical where a network needs to be deployed rapidly, or where there are too many unknown factors such as difficult environmental conditions or unpredictable spatial distribution of the network elements. Such factors are of particular relevance in situations such as disaster relief or battlefield situations, where there is insufficient time or information to plan the deployment of the resources. Advance planning is also impractical in circumstances where the devices themselves may move in unpredictable ways. For example, sensors may be distributed in an environment such that they are carried along with the movement of phenomena such as glaciers, ocean or atmospheric currents, lava flows, or wildlife, so that the behaviour of these phenomena can be monitored. Such sensors need to return the data they collect to a user.
In such circumstances, the network architecture cannot be planned in advance, but needs to be established in real time or close to it. In particular, the architecture has to be planned after the deployment of the hardware. In such circumstances, an “ad hoc” network architecture has to be developed. This can be achieved by having the individual devices negotiate amongst themselves so as to evolve a set of interconnections that can subsequently be used to pass information across the entire population of devices. Since the individual devices cannot have an overview of the whole network, (at least until the network is operational) each device can only use information that it can obtain for itself.
Many such ad-hoc networks involve mobile devices, which require constant updates to the web of interactions. However, this approach can also be used for the deployment of static devices, in circumstances in which there is no pre-existing network infrastructure, such as in disaster-relief operations or the deployment of sensors in order to survey large, potentially hostile environments such as volcanoes or enemy territory.
For many applications in which ad hoc networks are useful there is no pre-existing cabled medium, either for communications or power supply purposes. Most ad hoc networks therefore have to operate more or less exclusively through wireless communication, (usually radio), and the individual devices have to have their own power sources. Wireless connection offers many opportunities of fine-tuning through the use of multiple frequencies, time slicing and/or variable transmission power. However, it also adds complexity to the problem of achieving successful, robust and durable network integration, due to interference and limited battery lifetime. An important objective is to arrange that all nodes of the emerging network are mutually reachable over a long enough period to justify their deployment. As a result, identifying ways of preventing the formation of “islands” that cannot communicate with each other, due either to poor (indirect) long-range synchronisation or to the disappearance of key relays after they have exhausted their power supply, has become a high priority target in ad-hoc communication research.
There is therefore a need to configure the operation of the devices to mitigate the interference problem, while simultaneously managing battery power so as to ensure that the system as a whole can function for a sufficient time to be of any use. A difficulty resides in the fact that topological unpredictability dictates that nodes have to select their preferred frequency on the basis of local interactions only. This can be achieved through inhibitory signalling, as described in the applicant company's U.S. Pat. No. 6,539,228 and European patent 1074161. In this reference the devices exchange information with their neighbours or influence each other's preference. Alternatively, the devices may disregard frequencies that are already in use in their immediate vicinity. This process addresses interference in a single hop situation, such as between neighbouring base stations of a cellular radio network. In this situation the objective is to maintain stable connection between a first type of device (the fixed base stations) and a second type of device (the mobile phone units) at the interface between adjacent cells. This process ensures that immediate neighbours do not share the same frequency. In other words, it prevents overlap between adjacent regions, which is enough to organise frequency allocation between base stations that are meant to exchange information with a second type of device, such as fixed cellular base stations co-operating with mobile phones.
However, such a process does not deal adequately with networks in which any two nodes can exchange information via a sequence of hops along stable radio connections. To ensure stable connections exist throughout the network, it is necessary that each node is capable of sending data to its immediate neighbours without the risk that the signal is corrupted on the receiver's end by collision with other incoming packets. Such networks require that any two devices operating on the same channel (frequency, timeslot etc) must not both be within range of a third device. A conflict can occur in this situation, even though the two devices are not within range of each other, since the third device will nevertheless experience co-channel interference. In other words, “second” neighbours should also not be allowed to use the same frequency. This requirement requires the ability to identify conflicts between transmitters that cannot detect each other directly in normal operation. This is difficult to achieve using local inhibitory signalling only.
One way around this synchronisation problem is through acknowledgement messages (“ACK”s). However, this introduces its own difficulties. One is that emitting ACKs consumes battery power, which can be a serious limitation in an ad-hoc environment where the devices are operating on battery power and are difficult to access. The second, more subtle but also more complex to deal with, is that ACKs themselves can collide or be lost, with permanent instability as a possible result. For example, an ACK message can be lost, causing the emitter to mistakenly assume that the original packet has not been received properly. This can lead the node to attempt a frequency shift that could in fact result in a collision on the receiver's end, which would clearly initiate a pathological loop of successive adjustments.
This can in fact be represented as a “tiling” problem, with the extra constraint that not only should adjacent regions never share the same channel, but neither should two regions which are both adjacent to a third one. FIG. 1 illustrates a simple example, in which the nodes are conveniently disposed in a rectilinear formation. Each tile represents a communication node positioned at its centre. The maximum range of each node lies between 1 and 1.4 times the grid spacing. With these limits, each device can only communicate with its closest neighbours in the grid, and not with those further away. Each node is to be allocated one of the five channels a, b, c, d, or e. Two tiled lattices are depicted. The left hand diagram obeys the condition “no immediate neighbours share the same channel”. (Two tiles are considered to be “immediate neighbours” if they share an edge, but not if they only share a corner). Thus two tiles may share the same channel, provided only that they are not immediate neighbours. This is relatively simple to arrange, as each device can communicate directly with its immediate neighbours and co-operate with them to avoid using the same channels. However. several examples may be seen of two tiles using the same channel and having a neighbour in common—a network node represented by that common neighbour would experience co-channel interference between transmissions from its two neighbours. Those two neighbours are not capable of communicating directly with each other to avoid this problem.
The right hand diagram of FIG. 1 satisfies the additional condition that “no second neighbours share the same channel”, (where a “second neighbour” of a given device is a “immediate neighbour” of another device which is itself an immediate neighbour of the given device). In this case any two tiles having the same channel allocation are separated by at least two other tiles—either in a straight line or in a “two across and one up” or “chess knight's move” relationship. Therefore no tile is adjacent to any two other tiles both allocated to the same channel. Such an arrangement would ensure that, for any node in the system, no collisions are possible at the receiver's end between its immediate neighbours.
The difficulty resides in arranging for such an arrangement to happen when each device has to select its operational channels only on the basis of locally available information. If each device only has information available to it relating to its immediate neighbours, a stable periodic pattern such as the one shown on the right hand side of FIG. 1 is not possible to achieve except fortuitously. The problem, then, is how to get two devices to co-operate with each other to avoid interference, when such interference can occur in circumstances in which the devices cannot detect each other directly.
According to the invention, there is provided a wireless communications relay device, comprising a receiver for detecting transmissions from other such devices, and a transmitter for transmitting signals at a first power level for normal traffic, and a higher, inhibition level, in order that its transmissions may be detected by other such devices over a wider area than its normal operating range. Preferably the device also has control means for selecting a channel and a transmission power on which the transmitter should operate, the control means may be arranged to inhibit the transmitter from selecting channels detected by the receiver.
According to another aspect, there is provided a method of channel selection in a network of wireless communications relay devices, wherein each device is inhibited from operating on a channel detectable on transmissions received from another such device, when operating at an inhibition transmission power, in order to inhibit other such devices from selecting the same channel, wherein the inhibition transmission power is higher than the normal transmission power of the devices such that selection of the same channel is inhibited over a wider area than the normal operating range of the device.
The channel selection process may be operated on a computer, programmed with the relative separations and characteristics of the devices, and having means to control the operation of the relay devices in accordance with the results of the selection process. The relative separations may be determined from position information, and may take into account other properties such as path length or attenuation. However, in a preferred arrangement each device performs the channel selection process for itself, each device being operable on a selected channel at the inhibition transmission power and being capable of detecting transmissions from other such devices on the selected channel.
Preferably each device selects a channel on which to attempt to operate, and each such device transmits on that channel and also monitors the channel for conflicting transmissions from other devices, and determines, from the conflicts detected, whether to operate on the same or a different channel.
In a preferred arrangement, the control means selects a channel for operation by an iterative process, in which a plurality of attempts to transmit on a selected channel that are made, and the probability of the channel being selected increases according to the number of such attempts on which no conflicting transmissions are detected by the receiver.
In the preferred embodiment, the process is iterative, a property associated with each device being updated according to the number of attempts to transmit on a given channel have detected interference on that channel, and the said property is then used to control a probabilistic function which determines whether to switch to a different channel for subsequent attempts. If the said property also satisfies a threshold value the device may switch to normal operation.
It may be arranged that devices which are unable to identify a suitable channel on which to operate are not allocated a channel.
This invention therefore provides devices equipped to solve the problem of interference beyond their normal range. As a result, stable links can be established across the network, which provides the basis for successful message passing between distant regions.
The available bandwidth may be divided into channels in any known way, such as frequency division, time division, or code division. The embodiments to be described use frequency and time division, but this should not be taken as limitative of the scope of the invention.
Inhibition is preferably interpreted by the receiving node purely on the basis of received signal strength. It would be possible to base inhibition on information contained in a message, but this requires some degree of effective communication between the nodes in question to be in place already.
In the described embodiment the data relay devices are mobile devices communicating with each other using radio waves or other electromagnetic radiation, or by acoustic signals such as ultrasound. However, the invention may also be applied in a fixed-wire system.
The channel allocation process is thus carried out by the relay devices themselves, on the basis of information they can ascertain by interaction with a limited number of neighbours. The absence of an overall controlling function makes the invention equally suitable for networks with any number of elements since, at the level at which the computational process takes place, the scale of the problem is the same. To put it another way, the computational power required to process the allocation problem is in proportion to the number of elements in the network. Since the computation is in fact performed by those elements, the computational power available is also proportional to the number of elements in the network. Thus the computational overhead, as a proportion of the resources avaialable, is independent of the size of the network.